import java.util.ArrayList;
import java.util.Comparator;
import java.util.PriorityQueue;
/**
 * Created with IntelliJ IDEA
 * Description:
 * User: Administrator
 * Data: 2023 - 09 - 01
 * Time: 14:21
 */
//牛客 最小的K个数
public class Solution1 {
    //法一 我的方法
    public ArrayList<Integer> GetLeastNumbers_Solution (int[] input, int k) {
        ArrayList<Integer> arrayList = new ArrayList<>();
        if(k == 0) return arrayList;
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
        for (int i = 0; i < input.length; i++) {
            priorityQueue.offer(input[i]);
        }
        for (int j = 0; j < k; j++) {
            arrayList.add(priorityQueue.poll());
        }
        return arrayList;
    }


    //法二 官方推荐方法 维护大小为k的大根堆
    public ArrayList<Integer> GetLeastNumbers_Solution1(int [] input, int k) {
        ArrayList<Integer> res = new ArrayList<>();
        if(k == 0 || input.length == 0)
            return res;
        PriorityQueue<Integer> q = new PriorityQueue<>((o1, o2)->o2.compareTo(o1));//Lambda表达式的返回值为o2.compareTo(o1)，求最小的K个数要创建大根堆
        //构建一个k个大小的堆
        for(int i = 0; i < k; i++)
            q.offer(input[i]);
        for(int i = k; i < input.length; i++){
            //较小元素入堆
            if(q.peek() > input[i]){
                q.poll();
                q.offer(input[i]);
            }
        }
        //堆中元素取出入数组
        for(int i = 0; i < k; i++)
            res.add(q.poll());
        return res;
    }
}
